#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        bool flag = 0;
        queue<TreeNode*> que;
        if (root == nullptr) return {};
        que.push(root);

        vector<vector<int>> ret;
        while (que.size())
        {
            int n = que.size();
            vector<int> tmp;
            for (int i = 0; i < n; ++i)
            {
                TreeNode* tmpNode = que.front();
                que.pop();
                tmp.push_back(tmpNode->val);

                if (tmpNode->left != nullptr)
                {
                    que.push(tmpNode->left);
                }
                if (tmpNode->right != nullptr)
                {
                    que.push(tmpNode->right);
                }
            }
            if (flag == 1)
            {
                reverse(tmp.begin(), tmp.end());
                flag = 0;
            }
            else
                flag = 1;

            ret.push_back(tmp);
        }

        return ret;
    }
};